package newBee.class1;

import common.ArrayStack;
import common.ArrayUtils;


/**
 * 单调栈(Monotonic Stack)
 * <p>
 * arr1:[2, 5, 6, 7, 3, 4, 1, 8] 无重复
 * arr2:[2, 3, 4, 3, 2, 1, 3, 5, 6, 3, 4, 3, 2] 有重复
 * 1.求左、右比自己小的最近的数?
 * 解题思路
 */
public class Code01_LeftRightLess {
    public static void main(String[] args) {
        // demo1
        int[] arr = {2, 5, 6, 7, 3, 4, 1, 8};
        int[][] ans = leftRightLess(arr);
        ArrayUtils.printMatrixArr(ans);
        System.out.println("----------------------");

        // demo2
        int[] arr2 = {2, 3, 4, 3, 2, 1, 3, 5, 6, 3, 4, 3, 2};
        int[][] ans2 = leftRightLess(arr2);
        ArrayUtils.printMatrixArr(ans2);
    }

    public static int[][] leftRightLess(int[] arr) {

        ArrayStack stack = new ArrayStack(arr.length);
        int[][] ans = new int[arr.length][2];
        for (int i = 0; i < arr.length; i++) {
            // 栈不为空的情况下， 栈顶值 >= 即将入栈的值
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                // 将栈顶出栈
                int k = stack.pop();
                // 左边最近较小值
                ans[k][0] = !stack.isEmpty() ? stack.peek() : -1;
                // 右边最近较小值
                ans[k][1] = i;
            }
            stack.push(i);
        }
        // 阶段阶段
        while (!stack.isEmpty()) {
            // 出栈
            int k = stack.pop();
            // 倒数第二个出栈后，依旧栈顶有值，栈顶就是其最近较小值
            ans[k][0] = !stack.isEmpty() ? stack.peek() : -1;
            ans[k][1] = -1;
        }

        // 重复值清算
        for (int i = arr.length - 1; i >= 0; i--) {
            // 如果是-1则说明无右边较小值了，否则
            if (ans[i][1] != -1 && arr[ans[i][1]] == arr[i]) {
                ans[i][1] = ans[ans[i][1]][1];
            }
        }
        return ans;
    }

}
